package cxydmmszl.chapter01.t004;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <li style="color: red;">Prob</li>
 * 猫狗队列
 * <li style="color: green;">Desc</li>
 * 实现一种猫狗队列的结构，要求如下：<br/>
 * 1. 用户可以调用 add 方法将 cat 或者 dog 放入队列中<br/>
 * 2. 用户可以调用 pollAll 方法将队列中的 cat 和 dog 按照进队列的先后顺序依次弹出<br/>
 * 3. 用户可以调用 pollDog 方法将队列中的 dog 按照进队列的先后顺序依次弹出<br/>
 * 4. 用户可以调用 pollCat 方法将队列中的 cat 按照进队列的先后顺序依次弹出
 * 5. 用户可以调用 isEmpty 方法检查队列中是否还有 dog 或 cat<br/>
 * 6. 用户可以调用 isDogEmpty 方法检查队列中是否还有 dog<br/>
 * 7. 用户可以调用 isCatEmpty 方法检查队列中是否还有 cat
 * <br/><br/>备注：<br/>
 * 1≤n≤1000000<br/>
 * 保证每个猫和狗的编号x都不相同且1≤x≤1000000<br/>
 * 保证没有不合法的操作
 * <li style="color: green;">Input</li>
 * 第一行输入一个整数 n 表示 用户的操作总次数。<br/>
 * 以下 n行 每行表示用户的一次操作<br/>
 * 每行的第一个参数为一个字符串 s，若 s = “add”，
 * 则后面接着有“cat x”（表示猫）或者“dog x”（表示狗），其中的 x 表示猫狗的编号。
 * <li style="color: green;">Output</li>
 * 对于每个操作：<br/>
 * 若为 add，则不需要输出。<br/>
 * 以下仅列举几个代表操作，其它类似的操作输出同理。<br/>
 * 若为 pollAll，则将队列中的 cat 和 dog 按照进队列的先后顺序依次弹出。(FIFO)，格式见样例。<br/>
 * 若为 isEmpty，则检查队列中是否还有 dog 或 cat， 为空则输出 yes， 否则输出 no。
 * <li style="color: blue;">Link</li> CD100
 *
 * @author habitplus
 * @since 2021-08-13 22:27
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        DogCatQueue que = new DogCatQueue();
        StringBuilder sb = new StringBuilder();
        String[] ss;
        while (n-- > 0) {
            ss = br.readLine().split(" ");
            switch (ss[0]) {
                case "add":
                    int no = Integer.parseInt(ss[2]);
                    que.add(new Pet(ss[1], no));
                    break;
                case "pollAll":
                    List<Pet> pets = que.pollAll();
                    for (Pet p : pets) {
                        sb.append(p.getPetType()).append(" ").append(p.getNo()).append("\n");
                    }
                    break;
                case "pollDog":
                    while(!que.isDogQueueEmpty()) {
                        Pet dog = que.pollDog();
                        sb.append(dog.getPetType()).append(" ").append(dog.getNo()).append("\n");
                    }
                    break;
                case "pollCat":
                    while(!que.isCatQueueEmpty()) {
                        Pet cat = que.pollCat();
                        sb.append(cat.getPetType()).append(" ").append(cat.getNo()).append("\n");
                    }
                    break;
                case "isEmpty":
                    sb.append(que.isEmpty() ? "yes\n" : "no\n");
                    break;
                case "isCatEmpty":
                    sb.append(que.isCatQueueEmpty() ? "yes\n" : "no\n");
                    break;
                case "isDogEmpty":
                    sb.append(que.isDogQueueEmpty() ? "yes\n" : "no\n");
                    break;
                default:
                    System.out.println(233);
            }
        }
        System.out.println(sb.toString());
    }
}

class Pet {
    private String type;
    private int no;

    public Pet(String type, int no) {
        this.type = type;
        this.no = no;
    }

    public String getPetType() {
        return this.type;
    }

    public int getNo() {
        return this.no;
    }
}

class Dog extends Pet {
    public Dog(int no) {
        super("dog", no);
    }
}

class Cat extends Pet {
    public Cat(int no) {
        super("cat", no);
    }
}

/**
 * 自定义实现队列
 */
class PetEnterQueue {
    private Pet pet;
    private long timestamp;

    public PetEnterQueue(Pet pet, long timestamp) {
        this.pet = pet;
        this.timestamp = timestamp;
    }

    public Pet getPet() {
        return this.pet;
    }

    public long getTimestamp() {
        return this.timestamp;
    }

    public String getEnterPetType() {
        return this.pet.getPetType();
    }
}

class DogCatQueue {
    /**
     * 分别定义猫、狗队列
     */
    private Queue<PetEnterQueue> dogQ;
    private Queue<PetEnterQueue> catQ;
    private long count;

    public DogCatQueue() {
        this.dogQ = new LinkedList<>();
        this.catQ = new LinkedList<>();
        this.count = 0L;
    }

    public void add(Pet pet) {
        String t = pet.getPetType();
        if ("dog".equals(t)) {
            this.dogQ.add(new PetEnterQueue(pet, this.count++));
        } else if ("cat".equals(t)) {
            this.catQ.add(new PetEnterQueue(pet, this.count++));
        } else {
            throw new RuntimeException("不是猫或者狗！");
        }
    }

    public Pet poll() {
        if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
            if (this.dogQ.peek().getTimestamp() < this.catQ.peek().getTimestamp()) {
                return this.dogQ.poll().getPet();
            } else {
                return this.catQ.poll().getPet();
            }
        } else if (!this.dogQ.isEmpty()) {
            return this.dogQ.poll().getPet();
        } else if (!this.catQ.isEmpty()) {
            return this.catQ.poll().getPet();
        } else {
            throw new RuntimeException("Queue is empty!");
        }
    }

    public List<Pet> pollAll() {
        List<Pet> ansList = new ArrayList<>();
        while (!isEmpty()) {
            ansList.add(poll());
        }
        return ansList;
    }

    public Pet pollDog() {
        if (!this.isDogQueueEmpty()) {
            return this.dogQ.poll().getPet();
        } else {
            throw new RuntimeException("Dog queue is empty!");
        }
    }

    public Pet pollCat() {
        if (!this.isCatQueueEmpty()) {
            return this.catQ.poll().getPet();
        } else {
            throw new RuntimeException("Cat queue is empty!");
        }
    }

    public boolean isEmpty() {
        return this.dogQ.isEmpty() && this.catQ.isEmpty();
    }

    public boolean isCatQueueEmpty() {
        return this.catQ.isEmpty();
    }

    public boolean isDogQueueEmpty() {
        return this.dogQ.isEmpty();
    }

}
